Introduction to Computer Networks
Network Components
- component Names
- Network names by scale
Network Boundaries

- interface 1
- Sockets are widely used in practice
- interface 2
- Traceroute can peek in the network
Metcalfe’s Law
- The value of a network of N nodes is proportional to

Reference Models
- What functionality should we implement at which layer?
- Wires
- Twisted Pair
- Coaxial Cable
- Fiber (fiber optic cables)
- Two varieties: multi-mode (shorter links, cheaper) and single-mode (up to ~100 km)
- Wireless
- In many directions, unlike a wire, to potentially many receivers
- Nearby signals (same freq.) interfere at a receiver; need to coordinate use
Signals
- What happens to a signal as it passes over a wire?
- The signal is delayed (propagates at ⅔C)
- The signal is attenuated (goes for m to km)
- Frequencies above a cutoff are highly attenuated
- Noise is added to the signal (later, causes errors)
Modulation
- NRZ
- NRZI
- 4B/5B
- Manchester coding
baseband and passband
- baseband
- Signal is sent directly on a wire
- Passband
- These signals do not propagate well on fiber / wireless, Need to send at higher frequencies
- modify carrier by
- Amplitude
- frequency
- phase
Fundamental Limits
- Nyquist Limit(no noise channel)
- Shannon limit(noise channel)
- Wired/Wireless Perspective
Link Layer
Framing
- Byte count

- Difficult to re-synchronize after framing error
- Byte stuffing
- Have a special flag byte value that means start/end of frame
- Replace (“stuff”) the flag inside the frame with an escape code
- overhead
- Bit stuffing
- Call a flag six consecutive 1s
- On transmit, after five 1s in the data, insert a 0
- On receive, a 0 after five 1s is deleted
- practical link protocol(PPP)
How we deal with errors?
error detection + retransmit
- Parity
- Checksums
- IP, TCP, UDP … but it is weak
- CRCs
- CRCs are widely used on links
error correction
- Hamming code
- Convolutional codes
- Low Density Parity Check
Retransmissions
- ARQ
- Receiver automatically acknowledges correct frames with an ACK
- Sender automatically resends after a timeout, until an ACK is received
- Two non-trivial issues
- How long to set the timeout?
- Not too big (link goes idle)
- Not too small (spurious resend)
- How to avoid accepting duplicate frames as new frames?
- Sliding Window
- Allows W frames to be outstanding
Multiple Access
statistical multiplexing
- Time Division Multiplexing (TDM)
- Frequency Division Multiplexing (FDM)
- Network traffic is bursty, Inefficient to always allocate user their ON needs with TDM/FDM. — Multiple Access
Randomized. Nodes randomize their resource access attempts
Contention-free. Nodes order their resource access attempts
- They define an order in which nodes get a chance to send. We just need some ordering
- Token Ring

- Predictable service, easily extended to guaranteed quality of service
- Higher overhead at low load
- node addresses
error detection vs error correction
Network Layer
Overview
Network Service models

- Both models are implemented with store-and-forward packet switching
- Routers receive a complete packet, storing it temporarily if necessary before forwarding it onwards
- Internet的网络层协议(IP)采用的是数据报模型
- Datagram Model
- Packets contain a destination address; each router uses it to forward each packet, possibly on different paths
- Virtual Circuit Model
- Datagrams vs Virtual Circuits
- MPLS
Internetworking
- networks differ in many ways
- Service model (datagrams, VCs)
- Addressing (what kind)
- QOS (priorities, no priorities)
- Packet sizes
- Security (whether encrypted)
- solution: IP
- lowest common denominator
- Asks little of lower-layer networks
- Gives little as a higher layer service
Forwarding
- Longest Matching Prefix
- For each packet, find the longest prefix that contains the destination address, i.e., the most specific entry
- Forward the packet to the next hop router for that prefix
- host也可能需要转发,但是这个转发跟路由没有关系
Helping IP with ARP, DHCP
Packet Fragmentation
- How do we connect networks with different maximum packet sizes?
- Solutions
- fragment
- Path MTU Discovery
Error Handling with ICMP
- What happens when something goes wrong during forwarding? — ICMP
- ICMP is a companion protocol to IP
- They are implemented together
- Sits on top of IP (IP Protocol=1)



IPV6

- IPv6 Transition
- Fundamentally incompatible with IPv4
- Dual stack (speak IPv4 and IPv6)
- Translators (convert packets)
- Tunnels (carry IPv6 over IPv4)
NAT
- NAT is widely used at the edges of the network


Routing
- 实际上,路由完成的就是一个带宽分配的工作
- Delivery Models
- Goals of Routing Algorithms
- Rules of Routing Algorithms
Distance Vector Routing
- Simple, early routing approach

- News travels one hop per exchange
- problems:
- solution
- poison reverse
- Don’t send route back to where you learned it from
- Split horizon
Link State
flooding
Link-State Routing


- problems

Equal-Cost Multi-Path Routing
- Allow multiple routing paths from node to destination be used at once
- Topology has them for redundancy
- Using them can improve performance


Combining Hosts and Routers
- How routing protocols work with IP?

Hierarchical Routing
- Introduce a larger routing unit
- IP prefix (hosts) <— from one host
- Region, e.g., ISP network

IP Prefix Aggregation and Subnets
Routing with Multiple Parties
Transport Layer
TCP connection and disconnection
tcp and udp
connection establishment
connection release
Sliding Window Protocol
- Go-Back-N
- Selective Repeat


flow control
- Adding flow control to the sliding window algorithm
- Sender uses the lower of the sliding window and flow control window (WIN) as the effective window size
adaptive time-out
- How to set the timeout for sending a retransmission

tcp header

- Ports identify apps (socket API)
- SEQ/ACK used for sliding window
- SYN/FIN/RST flags for connections
- Window size for flow control
Congestion Control
- 什么是网络拥塞?
- 网络拥塞有什么后果?
- 控制网络拥塞本质上是一个带宽分配的问题,怎么在保证效率的同时保证公平?
- AIMD
ACK Clocking
- 实际上是一个滑动窗口,保证reliability

Fast Retransmit / Fast Recovery